In the field of automated recognition, automated recognition is performed by verifying a registered pattern with a pattern for verifying. The diversification of patterns in recent years has led to demands for technology capable of rapid alignment. For example, with the development of biometrics technology in recent years, various devices have been provided which recognize the characteristics of a body part which is a portion of a human body. In such devices, after aligning a pattern for verifying with a registered template, verifying is performed. For example, patterns such as fingerprints and toeprints, the retina of an eye, facial features, blood vessel patterns, and similar may be verified against a registered pattern to perform individual authentication.
In such verifying processing, the alignment processing time and precision are greatly affected by the processing time and precision of verifying processing.
In the prior art, various template matching methods have been proposed as pattern alignment techniques (see for example W. Rucklidge, “Efficient Visual Recognition Using the Hausdorff Distance”, Lecture Notes in Computer Science 1173, Springer-Verlag, 1996; Japanese Patent Laid-open No. 2003-30662; Japanese Patent Laid-open No. 5-233796).
The template matching methods employ an original pattern for comparison as a template, and perform operations to apply a target pattern for comparison to the template, and affine transformations and other techniques are utilized.
As other pattern alignment techniques, methods based on correspondence relationships and least-squares methods have also been proposed (see for example S. Belongie, J. Malik, J. Puzicha, “Shape Verifying and Object Recognition Using Shape Contexts”, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 24, No. 24, pp. 509 to 522, April 2002).
These are methods in which the Hungarian method or similar is employed for pattern correspondence relationships, to decide the optimum alignment based on predictions.
However, in methods of the prior art based on a template, patterns themselves are matched to the template, so that there are numerous geometrical conversion parameters for alignment. As the number of these geometric conversion parameters increases, processing time increases exponentially, so that there is the problem that long processing times are required. Moreover, there is the problem that global errors are large.
On the other hand, methods employing correspondence relationships and least-squares techniques require the Hungarian method or similar for calculation of correspondence relationships, so that processing times are lengthened, and moreover there is the problem that local errors are large.